Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

摘要

In this paper we demonstrate connections between three seemingly unrelatedconcepts. (1) The discrete isoperimetric problem in the infinite binary tree with allthe leaves at the same level, $ {\mathcal T}_{\infty}$: The $n$-th edge isoperimetric number $\delta(n)$ is defined to be$\min_{|S|=n, S \subset V({\mathcal T}_{\infty})} |(S,\bar{S})|$, where$(S,\bar{S})$ is the set of edges in the cut defined by $S$. (2) Signed almost binary partitions: This is the special case of thecoin-changing problem where the coins are drawn from the set ${\pm (2^d - 1): $d$ is a positive integer}$. The quantity of interest is$\tau(n)$, the minimum number of coins necessary to make change for $n$ cents. (3) Certain Meta-Fibonacci sequences: The Tanny sequence is defined by$T(n)=T(n{-}1{-}T(n{-}1))+T(n{-}2{-}T(n{-}2))$ and the Conolly sequence isdefined by $C(n)=C(n{-}C(n{-}1))+C(n{-}1{-}C(n{-}2))$, where the initialconditions are $T(1) = C(1) = T(2) = C(2) = 1$. These are well-known "meta-Fibonacci" sequences. The main result that ties these three together is the following: $$ \delta(n)= \tau(n) = n+ 2 + 2 \min_{1 \le k \le n} (C(k) - T(n-k) - k).$$ Apart fromthis, we prove several other results which bring out the interconnectionsbetween the above three concepts.